package leetcode20211023;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LUYAO
 * Date: 2021-10-23
 * Time: 16:42
 */
public class SlideMax {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,6,7};
        Solution231 s231 = new Solution231();
        int[] window = s231.maxSlidingWindow(nums, 3);
        for (int i = 0; i < window.length; i++) {
            System.out.println(window[i]);
        }


    }
}

//滑动窗口最大值
class Solution231 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> queue = new LinkedList<>();

        int res[] = new int[nums.length-k+1];
        //没有形成窗口
        for (int i = 0; i < k; i++) {
            while(!queue.isEmpty() && nums[i] > queue.peekLast()){
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }
        res[0] = queue.peekFirst();
        //形成窗口后
        for (int i = k; i < nums.length; i++) {
            if(nums[i-k] == queue.peekFirst()){
                queue.removeFirst();
            }
            while(!queue.isEmpty() && nums[i] > queue.peekLast()){
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            res[i - k + 1] = queue.peekFirst();
        }

        return res;

    }
}

//队列最大值
class MaxQueue {
    Deque<Integer> d;
    Queue<Integer> q;

    public MaxQueue() {
        d = new LinkedList<>();
        q = new LinkedList<>();

    }

    public int max_value() {
        if(d.isEmpty()){
            return -1;
        }
        return d.peekFirst();

    }

    public void push_back(int value) {
        while(!d.isEmpty() && value > d.peekLast()){
            d.removeLast();
        }
        d.addLast(value);
        q.add(value);


    }

    public int pop_front() {
        if(q.isEmpty()){
            return -1;
        }
        int ans = q.poll();
        if (ans == d.peekFirst()) {
            d.pollFirst();
        }
        return ans;


    }
}
